Рекуррентная формула чисел Стирлинга

$$ \begin{bmatrix} n+1 \\ k \end{bmatrix} = n \cdot \begin{bmatrix} n \\ k \end{bmatrix} + \begin{bmatrix} n \\ k-1 \end{bmatrix}, \text{ с начальными условиями } \begin{bmatrix} n \\ n \end{bmatrix} = 1 \text{ и } \begin{bmatrix} n \\ 0 \end{bmatrix} = 0~(n>0). $$

Для перестановок из $S_{n+1}$ с $k$ циклами есть 2 варианта. Если элемент $n+1$ образует отдельный цикл, то остальные $n$ элементов образуют $k-1$ циклов. Число таких перестановок равно $\begin{bmatrix} n \\ k-1 \end{bmatrix}$. Если элемент $n+1$ входит в неодноэлементный цикл, то его можно получить из перестановки $n$ элементов с $k$ циклами. В такую перестановку можно вставить $n+1$ в середину любого из $n$ ребер (например, заменив ребро $(i, j)$ на последовательность $(i, n+1, j)$). Таким образом, из каждой перестановки $n$ элементов с $k$ циклами можно получить $n$ различных перестановок $n+1$ элемента. Всего получим $n \cdot \begin{bmatrix} n \\ k \end{bmatrix}$ перестановок. Поскольку варианты исключают друг друга, по правилу суммы получаем: $$ \begin{bmatrix} n+1 \\ k \end{bmatrix} = n \cdot \begin{bmatrix} n \\ k \end{bmatrix} + \begin{bmatrix} n \\ k-1 \end{bmatrix} $$ $\square$